Spot-On
spot-on-pacify.h
1 /*
2 ** Copyright (c) 2011 - 10^10^10, Mattias AndrĂ©e, Alexis Megas.
3 ** All rights reserved.
4 **
5 ** Redistribution and use in source and binary forms, with or without
6 ** modification, are permitted provided that the following conditions
7 ** are met:
8 ** 1. Redistributions of source code must retain the above copyright
9 ** notice, this list of conditions and the following disclaimer.
10 ** 2. Redistributions in binary form must reproduce the above copyright
11 ** notice, this list of conditions and the following disclaimer in the
12 ** documentation and/or other materials provided with the distribution.
13 ** 3. The name of the author may not be used to endorse or promote products
14 ** derived from Spot-On without specific prior written permission.
15 **
16 ** SPOT-ON IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 ** SPOT-ON, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27 
28 #ifndef _spoton_pacify_h_
29 #define _spoton_pacify_h_
30 
31 #include <cmath>
32 #include <map>
33 #include <string>
34 
36 {
37  public:
38  spoton_pacify(const std::string &passphrase)
39  {
40  size_t n = passphrase.length();
41 
42  // Convert from UTF-8 to UTF-32.
43  // Note this is not an attack-safe implementation,
44  // this implementation allows characters that are
45  // encoded with an excessive number of bytes.
46 
47  // Count the number of characters.
48  // Byte Datum
49  // 0....... Single-byte character (Count these.)
50  // 11...... Initial byte in multibyte character (Count these.)
51  // 10...... Non-initial byte in multibyte character (Do not count these.)
52 
53  m_passphrase = 0;
54  m_passphrase_length = 0;
55 
56  for(size_t i = 0; i < n; i++)
57  if((static_cast<int> (passphrase.at(i)) & 0xc0) != 0x80)
58  m_passphrase_length += 1;
59 
60  if(m_passphrase_length > 0)
61  m_passphrase = new long int[m_passphrase_length];
62 
63  // Convert.
64  // 0.......
65  // 110..... 10......
66  // 1110.... 10...... 10......
67  // 11110... 10...... 10...... 10......
68  // 111110.. 10...... 10...... 10...... 10......
69  // 1111110. 10...... 10...... 10...... 10...... 10......
70 
71  for(size_t i = 0, j = 0; i < n; j++)
72  {
73  int c = static_cast<int> (passphrase.at(i++));
74 
75  if((c & 0x80) == 0)
76  {
77  // Single-byte character.
78 
79  if(m_passphrase)
80  m_passphrase[j] = static_cast<long int> (c);
81  }
82  else if((c & 0xc0) == 0xc0)
83  {
84  // Initial byte in multibyte-character.
85 
86  int b = 0;
87 
88  // Get width of character.
89  // 110..... 2-byte character 11-bit character
90  // 1110.... 3-byte character 16-bit character
91  // 11110... 4-byte character 21-bit character (New UTF-8 Limit)
92  // 111110.. 5-byte character 26-bit character
93  // 1111110. 6-byte character 31-bit character (Old UTF-8 Limit)
94 
95  while(c & 0x80)
96  b++, c <<= 1;
97 
98  if(b > 6)
99  {
100  if(m_passphrase)
101  m_passphrase[j] = 0; /* XXX invalid input. */
102 
103  break;
104  }
105 
106  // Get bits (represented by dots in the table above)
107  // stored in the start byte.
108 
109  c = (c & 0xff) >> b;
110 
111  if(m_passphrase)
112  m_passphrase[j] = static_cast<long int> (c);
113 
114  // We have read one of the bytes.
115 
116  b--;
117 
118  // Get bits stored in the continuation bytes.
119  // 10......
120 
121  while(b--)
122  {
123  if(i == n)
124  {
125  // Premature end of string.
126 
127  if(m_passphrase)
128  m_passphrase[j] = 0; /* XXX invalid input. */
129 
130  break;
131  }
132 
133  c = static_cast<int> (passphrase.at(i++));
134 
135  if((c & 0xc0) != 0x80)
136  {
137  // Premature end of multibyte-character byte sequence.
138 
139  if(m_passphrase)
140  m_passphrase[j] = 0; /* XXX invalid input. */
141 
142  i--;
143  break;
144  }
145  else
146  {
147  // Store the six lowest bits.
148 
149  if(m_passphrase)
150  {
151  m_passphrase[j] <<= 6;
152  m_passphrase[j] |= static_cast<long int> (c & 0x3f);
153  }
154  }
155  }
156  }
157  else
158  // Non-initial byte in multibyte-character at beginning of character.
159  // (Unexpected continuation byte.)
160 
161  j--; /* XXX invalid input. */
162  }
163  }
164 
165  ~spoton_pacify()
166  {
167  delete []m_passphrase;
168  }
169 
170  double evaluate(void) const
171  {
172  if(!m_passphrase || m_passphrase_length == 0)
173  return 25.0; // Error!
174 
175  double rc = 0.0;
176  long int last = -1;
177  std::map<long int, int> used;
178  std::map<double, int> classes;
179 
180  classes[2.5] = 0;
181  classes[3.5] = 0;
182 
183  for(int i = 1; i <= 10; i++)
184  classes[i] = 0;
185 
186  for(size_t i = 0; i < m_passphrase_length; i++)
187  {
188  double r = 0.0;
189  long int c = m_passphrase ? m_passphrase[i] : 0;
190 
191  r = char_class(c);
192 
193  if(used.end() == used.find(c))
194  used[c] = 1;
195  else
196  used[c] += 1;
197 
198  rc += std::pow(r, 2);
199  rc += 5.0 / used[c];
200 
201  if(r >= 4.0)
202  r += 2.0;
203  else if(r > 3.0)
204  r = 5.0;
205  else if(qFuzzyCompare(3.0, r))
206  r = 4.0;
207  else if(r > 2.0)
208  r = 3.0;
209 
210  if(classes.end() == classes.find(r - 1.0))
211  classes[r - 1.0] = 0;
212 
213  classes[r - 1.0] += 1;
214 
215  if(i > 0)
216  {
217  if(c > 127 || last > 127)
218  r = distance('\0', '\0');
219  else
220  r = distance(static_cast<char> (c), static_cast<char> (last));
221 
222  rc += std::pow(r, 0.5);
223  }
224 
225  last = c;
226  }
227 
228  if(rc >= 0.0)
229  rc += 30.0;
230 
231  double a = 0.0;
232  double b = 0.0;
233  double c = 0.0;
234  double d = 0.0;
235  int i = 0;
236 
237  for(std::map<double, int>::iterator it = classes.begin();
238  it != classes.end(); i++, it++)
239  if(i == 0)
240  a = it->second;
241  else if(i == 1)
242  b = it->second;
243  else if(i == 2)
244  c = it->second;
245  else if(i == 3)
246  d = it->second;
247  else
248  break;
249 
250  if(qFuzzyIsNull(a + b + c + d))
251  rc += 30.0;
252  else
253  {
254  double r = std::pow(a, 2) + std::pow(b, 2) + std::pow(c, 3) +
255  std::pow(d, 2);
256 
257  rc += 30.0 * static_cast<double> (m_passphrase_length) /
258  std::pow(r, 0.5);
259  }
260 
261  return std::floor(rc + 0.5);
262  }
263 
264  private:
265  long int *m_passphrase;
266  size_t m_passphrase_length;
267 
268  double char_class(const long int c) const
269  {
270  if(static_cast<long int> ('0') <= c && c <= static_cast<long int> ('9'))
271  return 1.0;
272  else if(static_cast<long int> ('a') <= c &&
273  c <= static_cast<long int> ('z'))
274  return 2.0;
275  else if(static_cast<long int> ('A') <= c &&
276  c <= static_cast<long int> ('Z'))
277  return 2.5;
278  else if(c < (1 << 7))
279  return 3.0;
280  else if(c < (1 << 8))
281  return 3.5;
282  else if(c < (1 << 10))
283  return 4.0;
284  else if(c < (1 << 14))
285  return 5.0;
286  else if(c < (1 << 16))
287  return 6.0;
288  else if(c < (1 << 18))
289  return 7.0;
290  else if(c < (1 << 22))
291  return 8.0;
292  else if(c < (1 << 26))
293  return 9.0;
294  else
295  return 10.0;
296  }
297 
298  double distance(const char a, const char b) const
299  {
300  std::string _a_;
301  std::string _b_;
302 
303  _a_.append(1, a);
304  _b_.append(1, b);
305  std::transform(_a_.begin(), _a_.end(), _a_.begin(), ::tolower);
306  std::transform(_b_.begin(), _b_.end(), _b_.begin(), ::tolower);
307 
308  if(_a_ == _b_)
309  return 0.0;
310 
311  std::map<char, std::pair<double, double> > keys;
312  std::string L1("1234567890");
313  std::string L2("qwertyuiop");
314  std::string L3("asdfghjkl");
315  std::string L4("zxcvbnm");
316  std::string _a_b_(_a_ + _b_);
317 
318  for(size_t i = 0; i < L1.length(); i++)
319  keys[L1[i]] = std::pair<double, double> (static_cast<double> (i), 0.0);
320 
321  for(size_t i = 0; i < L2.length(); i++)
322  keys[L2[i]] = std::pair<double, double> (static_cast<double> (i) + 0.5,
323  1.0);
324 
325  for(size_t i = 0; i < L3.length(); i++)
326  keys[L3[i]] = std::pair<double, double> (static_cast<double> (i) + 0.75,
327  2.0);
328 
329  for(size_t i = 0; i < L4.length(); i++)
330  keys[L4[i]] = std::pair<double, double> (static_cast<double> (i) + 1.0,
331  3.0);
332 
333  for(size_t i = 0; i < _a_b_.length(); i++)
334  if(keys.end() == keys.find(_a_b_[i]))
335  return 15.0;
336 
337  return std::pow(std::pow(keys[_a_.at(0)].first -
338  keys[_b_.at(0)].first, 2) +
339  std::pow(keys[_a_.at(0)].second -
340  keys[_b_.at(0)].second, 2), 0.5);
341  }
342 };
343 
344 #endif
spoton_pacify
Definition: spot-on-pacify.h:35